<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  
  <title>hashmap | 华锅锅的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  
    <meta name="keywords" content="Huaguoguo,Huaguoguo's Blog">
  
  <meta name="description" content="HashMap问题 黑红树变色和旋转 为什么还有数组+链表的结构而不是一开始就红黑树结构   红黑树红黑树的特性 根节点与叶节点都是黑色节点，其中叶节点为Null节点 每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点 从根节点到所有叶子节点上的黑色节点数量是相同的  上述的性质约束了红黑树的关键：从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是:">
<meta name="keywords" content="java,集合">
<meta property="og:type" content="article">
<meta property="og:title" content="hashmap">
<meta property="og:url" content="http://huaguoguo.gitee.io/2019/07/04/hashmap/index.html">
<meta property="og:site_name" content="华锅锅的博客">
<meta property="og:description" content="HashMap问题 黑红树变色和旋转 为什么还有数组+链表的结构而不是一开始就红黑树结构   红黑树红黑树的特性 根节点与叶节点都是黑色节点，其中叶节点为Null节点 每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点 从根节点到所有叶子节点上的黑色节点数量是相同的  上述的性质约束了红黑树的关键：从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是:">
<meta property="og:locale" content="default">
<meta property="og:image" content="https://huaguoguo.gitee.io/images/tree/rbt-insert.png">
<meta property="og:updated_time" content="2019-07-04T12:44:20.970Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="hashmap">
<meta name="twitter:description" content="HashMap问题 黑红树变色和旋转 为什么还有数组+链表的结构而不是一开始就红黑树结构   红黑树红黑树的特性 根节点与叶节点都是黑色节点，其中叶节点为Null节点 每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点 从根节点到所有叶子节点上的黑色节点数量是相同的  上述的性质约束了红黑树的关键：从根到叶子的最长可能路径不多于最短可能路径的两倍长。得到这个结论的理由是:">
<meta name="twitter:image" content="https://huaguoguo.gitee.io/images/tree/rbt-insert.png">
  
  
    <link rel="icon" href="/favicon.ico">
  
  <link href="//cdn.bootcss.com/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet" type="text/css">
  <link rel="stylesheet" href="/css/style.css">
  <script src="/js/pace.min.js"></script>
  

  
  

</head>
</html>
<body>
  <div id="container">
      <header id="header">
    <div id="banner"></div>
    <div id="header-outer">
        <div id="header-menu" class="header-menu-pos animated">
            <div class="header-menu-container">
                <a href="/" class="left">
                    <span class="site-title">Huaguoguo&#39;s Blog</span>
                </a>
                <nav id="header-menu-nav" class="right">
                    
                    <a href="/">
                        <i class="fa fa-home"></i>
                        <span>Home</span>
                    </a>
                    
                    <a href="/archives">
                        <i class="fa fa-archive"></i>
                        <span>Archives</span>
                    </a>
                    
                    <a href="/about">
                        <i class="fa fa-user"></i>
                        <span>About</span>
                    </a>
                    
                </nav>
                <a class="mobile-header-menu-button">
                    <i class="fa fa-bars"></i>
                </a>
            </div>
        </div>
        <div id="header-row">
            <div id="logo">
                <a href="/">
                    <img src="/images/logo.png" alt="logo">
                </a>
            </div>
            <div class="header-info">
                <div id="header-title">
                    
                    <h2>
                        Huaguoguo&#39;s Blog
                    </h2>
                    
                </div>
                <div id="header-description">
                    
                    <h3>
                        敲代码是热爱，敲到世界充满爱
                    </h3>
                    
                </div>
            </div>
            <nav class="header-nav">
                <div class="social">
                    
                        <a title="home" target="_blank" href="//huaguoguo.gitee.io">
                            <i class="fa fa-home fa-2x"></i></a>
                    
                        <a title="Github" target="_blank" href="//gitee.com/huaguoguo">
                            <i class="fa fa-github fa-2x"></i></a>
                    
                </div>
            </nav>
        </div>
    </div>
</header>
      <div class="outer">
        <section id="main" class="body-wrap"><article id="post-hashmap" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-inner">
    
      <header class="article-header">
        
  
    <h1 class="post-title" itemprop="name">
      hashmap
    </h1>
    <div class="post-title-bar">
      <ul>
          
              <li>
                  <i class="fa fa-book"></i>
                  
                      <a href="/categories/First/">First</a>
                  
              </li>
          
        <li>
          <i class="fa fa-calendar"></i>  2019-07-04
        </li>
        <li>
          <i class="fa fa-eye"></i>
          <span id="busuanzi_value_page_pv"></span>
        </li>
      </ul>
    </div>
  

          
      </header>
    
    <div class="article-entry post-content" itemprop="articleBody">
      
            
            <h2 id="HashMap"><a href="#HashMap" class="headerlink" title="HashMap"></a>HashMap</h2><h3 id="问题"><a href="#问题" class="headerlink" title="问题"></a>问题</h3><ol>
<li>黑红树变色和旋转</li>
<li>为什么还有数组+链表的结构而不是一开始就红黑树结构</li>
<li></li>
</ol>
<h3 id="红黑树"><a href="#红黑树" class="headerlink" title="红黑树"></a>红黑树</h3><h4 id="红黑树的特性"><a href="#红黑树的特性" class="headerlink" title="红黑树的特性"></a>红黑树的特性</h4><ol>
<li>根节点与叶节点都是黑色节点，其中叶节点为Null节点</li>
<li>每个红色节点的两个子节点都是黑色节点，换句话说就是不能有连续两个红色节点</li>
<li>从根节点到所有叶子节点上的黑色节点数量是相同的</li>
</ol>
<p>上述的性质约束了红黑树的关键：<strong>从根到叶子的最长可能路径不多于最短可能路径的两倍长</strong>。得到这个结论的理由是:</p>
<ol>
<li>红黑树中最短的可能路径是全部为黑色节点的路径</li>
<li>红黑树中最长的可能路径是红黑相间的路径</li>
</ol>
<p>最终保证了红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除。</p>
<h4 id="添加数据"><a href="#添加数据" class="headerlink" title="添加数据"></a>添加数据</h4><p>步骤：</p>
<ol>
<li>获取根节点，根节点为空，产生一个根节点，将其着色为黑色，退出余下流程</li>
<li>获取比较器，如果传入的Comparator接口不为空，使用传入的Comparator接口实现<br>类进行比较；如果传入的Comparator接口为空，将Key强转为Comparable接口进行比较</li>
<li>从根节点开始逐一依照规定的排序算法进行比较，取比较值cmp，如果cmp=0，表示插入的Key已存在；如果cmp&gt;0，取当前节点的右子节点；如果cmp&lt;0，取当前节点的左子节点</li>
<li>排除插入的Key已存在的情况，第（3）步的比较一直比较到当前节点t的左子节点或右子节点为null，此时t就是我们寻找到的节点，cmp&gt;0则准备往t的右子节点插入新节点，cmp&lt;0则准备往t的左子节点插入新节点</li>
<li>new出一个新节点，默认为黑色，根据cmp的值向t的左边或者右边进行插入</li>
<li>插入之后进行修复，包括左旋、右旋、重新着色这些操作，让树保持平衡性</li>
</ol>
<p>重点在第六步的修复，以插入元素为例：<br><img src="https://huaguoguo.gitee.io/images/tree/rbt-insert.png" alt="插入修复流程图"></p>
<p>旋转的几个性质:</p>
<ol>
<li>左旋和右旋是对称的操作</li>
<li>以左旋为例：对x节点进行左旋，x将变成当前位置的左子节点</li>
<li>插入时，命名插入的节点为x，左旋对象是x的父节点，右旋对象是x的祖父节点（<strong>左旋转爸爸，右旋转爷爷</strong>）</li>
</ol>
<p><a href="https://www.cs.usfca.edu/~galles/visualization/Algorithms.html" target="_blank" rel="noopener">动画演示网站</a>（各种数据结构可视化演示，赞！！！）</p>
<h4 id="删除数据"><a href="#删除数据" class="headerlink" title="删除数据"></a>删除数据</h4><p>步骤：</p>
<ol>
<li><strong>将红黑树当作一颗二叉查找树，将节点删除</strong><br><br> 这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：<ol>
<li>被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。</li>
<li>被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。</li>
<li>被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给”被删除节点”之后，再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了，下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空，就意味着”该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况① “进行处理；若只有一个儿子，则按”情况② “进行处理。(目前发现是左儿子顶替了爸爸的位置，这个后续再研究)</li>
</ol>
</li>
<li><strong>通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树</strong><br><br> 与插入类型，根据红黑树的特效去进行平衡</li>
</ol>

            <div class="post-copyright">
    <div class="content">
        <p>最后更新： 2019年07月04日 20:44</p>
        <p>原始链接： <a class="post-url" href="/2019/07/04/hashmap/" title="hashmap">http://huaguoguo.gitee.io/2019/07/04/hashmap/</a></p>
        <footer>
            <a href="http://huaguoguo.gitee.io">
                <img src="/images/logo.png" alt="华锅锅">
                华锅锅
            </a>
        </footer>
    </div>
</div>

      
        
            
<div class="page-reward">
    <a id="rewardBtn" href="javascript:;">赏</a>
</div>

<div id="reward" class="post-modal reward-lay">
    <a class="close" href="javascript:;" id="reward-close">×</a>
    <span class="reward-title">
        <i class="icon icon-quote-left"></i>
        请我吃糖~
        <i class="icon icon-quote-right"></i>
    </span>
    <div class="reward-content">
        
        <div class="reward-code">
            <img id="rewardCode" src="/images/wechat_code.png" alt="打赏二维码">
        </div>
        <div class="reward-select">
            
            <label class="reward-select-item checked" data-id="wechat" data-wechat="/images/wechat_code.png">
                <img class="reward-select-item-wechat" src="/images/wechat.png" alt="微信">
            </label>
            
            
            <label class="reward-select-item" data-id="alipay" data-alipay="/images/alipay_code.png">
                <img class="reward-select-item-alipay" src="/images/alipay.png" alt="支付宝">
            </label>
            
        </div>
    </div>
</div>


        
    </div>
    <footer class="article-footer">
        
        
<div class="post-share">
    <a href="javascript:;" id="share-sub" class="post-share-fab">
        <i class="fa fa-share-alt"></i>
    </a>
    <div class="post-share-list" id="share-list">
        <ul class="share-icons">
          <li>
            <a class="weibo share-sns" target="_blank" href="http://service.weibo.com/share/share.php?url=http://huaguoguo.gitee.io/2019/07/04/hashmap/&title=《hashmap》 — 华锅锅的博客&pic=/images/tree/red-black-tree.jpg" data-title="微博">
              <i class="fa fa-weibo"></i>
            </a>
          </li>
          <li>
            <a class="weixin share-sns" id="wxFab" href="javascript:;" data-title="微信">
              <i class="fa fa-weixin"></i>
            </a>
          </li>
          <li>
            <a class="qq share-sns" target="_blank" href="http://connect.qq.com/widget/shareqq/index.html?url=http://huaguoguo.gitee.io/2019/07/04/hashmap/&title=《hashmap》 — 华锅锅的博客&source=敲代码是热爱，敲到世界充满爱" data-title="QQ">
              <i class="fa fa-qq"></i>
            </a>
          </li>
          <li>
            <a class="facebook share-sns" target="_blank" href="https://www.facebook.com/sharer/sharer.php?u=http://huaguoguo.gitee.io/2019/07/04/hashmap/" data-title="Facebook">
              <i class="fa fa-facebook"></i>
            </a>
          </li>
          <li>
            <a class="twitter share-sns" target="_blank" href="https://twitter.com/intent/tweet?text=《hashmap》 — 华锅锅的博客&url=http://huaguoguo.gitee.io/2019/07/04/hashmap/&via=http://huaguoguo.gitee.io" data-title="Twitter">
              <i class="fa fa-twitter"></i>
            </a>
          </li>
          <li>
            <a class="google share-sns" target="_blank" href="https://plus.google.com/share?url=http://huaguoguo.gitee.io/2019/07/04/hashmap/" data-title="Google+">
              <i class="fa fa-google-plus"></i>
            </a>
          </li>
        </ul>
     </div>
</div>
<div class="post-modal wx-share" id="wxShare">
    <a class="close" href="javascript:;" id="wxShare-close">×</a>
    <p>扫一扫，分享到微信</p>
    <img src="//api.qrserver.com/v1/create-qr-code/?data=http://huaguoguo.gitee.io/2019/07/04/hashmap/" alt="微信分享二维码">
</div>

<div class="mask"></div>

        
        <ul class="article-footer-menu">
            
            
  <li class="article-footer-tags">
    <i class="fa fa-tags"></i>
      
    <a href="/tags/java/" class="color5">java</a>
      
    <a href="/tags/集合/" class="color3">集合</a>
      
  </li>

        </ul>
        
    </footer>
  </div>
</article>


    <aside class="post-toc-pos post-toc-top" id="post-toc">
        <nav class="post-toc-wrap">
            <ol class="post-toc"><li class="post-toc-item post-toc-level-2"><a class="post-toc-link" href="#HashMap"><span class="post-toc-text">HashMap</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#问题"><span class="post-toc-text">问题</span></a></li><li class="post-toc-item post-toc-level-3"><a class="post-toc-link" href="#红黑树"><span class="post-toc-text">红黑树</span></a><ol class="post-toc-child"><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#红黑树的特性"><span class="post-toc-text">红黑树的特性</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#添加数据"><span class="post-toc-text">添加数据</span></a></li><li class="post-toc-item post-toc-level-4"><a class="post-toc-link" href="#删除数据"><span class="post-toc-text">删除数据</span></a></li></ol></li></ol></li></ol>
        </nav>
    </aside>
    

<nav id="article-nav">
  
    <a href="/2019/07/08/index-study/" id="article-nav-newer" class="article-nav-link-wrap">

      <span class="article-nav-title">
        <i class="fa fa-hand-o-left" aria-hidden="true"></i>
        
          索引整理
        
      </span>
    </a>
  
  
    <a href="/2019/05/15/study/" id="article-nav-older" class="article-nav-link-wrap">
      <span class="article-nav-title">学习建议</span>
      <i class="fa fa-hand-o-right" aria-hidden="true"></i>
    </a>
  
</nav>



    
        <div id="SOHUCS" sid="hashmap"></div>
<script type="text/javascript">
    (function(){
        var appid = 'cyudxaFKB';
        var conf = 'e3991feeac8273781b96fbec365fe014';
        var width = window.innerWidth || document.documentElement.clientWidth;
        if (width < 960) {
            window.document.write('<script id="changyan_mobile_js" charset="utf-8" type="text/javascript" src="https://changyan.sohu.com/upload/mobile/wap-js/changyan_mobile.js?client_id=' + appid + '&conf=' + conf + '"><\/script>'); } else { var loadJs=function(d,a){var c=document.getElementsByTagName("head")[0]||document.head||document.documentElement;var b=document.createElement("script");b.setAttribute("type","text/javascript");b.setAttribute("charset","UTF-8");b.setAttribute("src",d);if(typeof a==="function"){if(window.attachEvent){b.onreadystatechange=function(){var e=b.readyState;if(e==="loaded"||e==="complete"){b.onreadystatechange=null;a()}}}else{b.onload=a}}c.appendChild(b)};loadJs("https://changyan.sohu.com/upload/changyan.js",function(){window.changyan.api.config({appid:appid,conf:conf})}); } })(); </script>
    
</section>
        
      </div>
      <footer id="footer">
  <div class="outer">
    <div id="footer-info" class="inner">
      
<p>
    <span id="busuanzi_container_site_uv" style="display:none">
        总访客数：<span id="busuanzi_value_site_uv"></span>
    </span>
    <span id="busuanzi_container_site_pv" style="display:none">
        总访问量：<span id="busuanzi_value_site_pv"></span>
    </span>
</p>


      <p>
        Powered by  <a href="http://hexo.io/" target="_blank">Hexo</a>
        Theme <a href="//github.com/wongminho/hexo-theme-miho" target="_blank">MiHo</a>
      &copy; 2020 华锅锅<br>
      </p>
    </div>
  </div>
</footer>
    <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
<script src="//cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>
<script>
  var mihoConfig = {
      root: "http://huaguoguo.gitee.io",
      animate: true,
      isHome: false,
      share: true,
      reward: 1
  }
</script>
<div class="sidebar">
    <div id="sidebar-search" title="Search">
        <i class="fa fa-search"></i>
    </div>
    <div id="sidebar-category" title="Categories">
        <i class="fa fa-book"></i>
    </div>
    <div id="sidebar-tag" title="Tags">
        <i class="fa fa-tags"></i>
    </div>
    <div id="sidebar-top">
        <span class="sidebar-top-icon"><i class="fa fa-angle-up"></i></span>
    </div>
</div>
<div class="sidebar-menu-box" id="sidebar-menu-box">
    <div class="sidebar-menu-box-container">
        <div id="sidebar-menu-box-categories">
            <a class="category-link" href="/categories/First/">First</a>
        </div>
        <div id="sidebar-menu-box-tags">
            <a href="/tags/Hexo/" style="font-size: 10px;">Hexo</a> <a href="/tags/Sample/" style="font-size: 10px;">Sample</a> <a href="/tags/java/" style="font-size: 20px;">java</a> <a href="/tags/分布式/" style="font-size: 15px;">分布式</a> <a href="/tags/学习方法/" style="font-size: 10px;">学习方法</a> <a href="/tags/数据库/" style="font-size: 15px;">数据库</a> <a href="/tags/缓存/" style="font-size: 10px;">缓存</a> <a href="/tags/集合/" style="font-size: 10px;">集合</a>
        </div>
    </div>
    <a href="javascript:;" class="sidebar-menu-box-close">&times;</a>
</div>
<div class="mobile-header-menu-nav" id="mobile-header-menu-nav">
    <div class="mobile-header-menu-container">
        <span class="title">Menus</span>
        <ul class="mobile-header-menu-navbar">
            
            <li>
                <a href="/">
                    <i class="fa fa-home"></i><span>Home</span>
                </a>
            </li>
            
            <li>
                <a href="/archives">
                    <i class="fa fa-archive"></i><span>Archives</span>
                </a>
            </li>
            
            <li>
                <a href="/about">
                    <i class="fa fa-user"></i><span>About</span>
                </a>
            </li>
            
        </ul>
    </div>
    <div class="mobile-header-tag-container">
        <span class="title">Tags</span>
        <div id="mobile-header-container-tags">
            <a href="/tags/Hexo/" style="font-size: 10px;">Hexo</a> <a href="/tags/Sample/" style="font-size: 10px;">Sample</a> <a href="/tags/java/" style="font-size: 20px;">java</a> <a href="/tags/分布式/" style="font-size: 15px;">分布式</a> <a href="/tags/学习方法/" style="font-size: 10px;">学习方法</a> <a href="/tags/数据库/" style="font-size: 15px;">数据库</a> <a href="/tags/缓存/" style="font-size: 10px;">缓存</a> <a href="/tags/集合/" style="font-size: 10px;">集合</a>
        </div>
    </div>
</div>
<div class="search-wrap">
    <span class="search-close">&times;</span>
        <a href="javascript:;" class="header-icon waves-effect waves-circle waves-light" id="back">
            <i class="icon icon-lg icon-chevron-left"></i>
        </a>
        <input class="search-field" placeholder="Search..." id="keywords">
        <a id="search-submit" href="javascript:;">
            <i class="fa fa-search"></i>
        </a>
    <div class="search-container" id="search-container">
        <ul class="search-result" id="search-result">
        </ul>
    </div>
</div>

<div id="search-tpl">
    <li class="search-result-item">
        <a href="{url}" class="search-item-li">
            <span class="search-item-li-title" title="{title}">{title}</span>
        </a>
    </li>
</div>
<script src="/js/search.js"></script>
<script src="/js/main.js"></script>


  <script src="//cdn.bootcss.com/particles.js/2.0.0/particles.min.js"></script>
  <div id="particles"></div>
  <script src="/js/particles.js"></script>







  <link rel="stylesheet" href="//cdn.bootcss.com/animate.css/3.5.0/animate.min.css">
  <script src="//cdn.bootcss.com/scrollReveal.js/3.0.5/scrollreveal.js"></script>
  <script src="/js/animate.js"></script>


  <script src="/js/pop-img.js"></script>
  <script>
     $(".article-entry p img").popImg();
  </script>

  </div>
</body>
</html>